package test;

import java.util.ArrayList;
import java.util.List;

//组合总和：https://leetcode.cn/problems/combination-sum/
public class CombinationSum {
	public List<List<Integer>> ret;
    public List<Integer> path;
    public void dfs(int[] nums,int target,int pos,int sum){
        if(pos==nums.length||sum>=target){
            if(sum==target)
                ret.add(new ArrayList(path));
            return ;
        }
        //本题是不考虑顺序的，而3,2等价于2,3，因此每次只枚举i位置及其后面的位置；
        for(int i=pos;i<nums.length;i++){
            path.add(nums[i]);
            //传i而不是i+1,因为可以枚举自身
            dfs(nums,target,i,sum+nums[i]);
            path.remove(path.size()-1);
        }
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        ret=new ArrayList<>();
        path=new ArrayList();
        dfs(candidates,target,0,0);
        return ret;
    }
}
